#region using statements

using System;
using System.Collections.Generic;

#endregion

namespace NGen.Collections
{
	/// <summary>
	/// 	Priority Queue implementation using a heap
	/// </summary>
	public class PriorityQueue<T>
		where T : IComparable<T>
	{
		#region local fields

		/// <summary>
		/// 	storage container for all of the objects in the queue
		/// </summary>
		private readonly List<T> m_queueContents;

		#endregion

		#region properties

		/// <summary>
		/// 	Gets the number of objects in the queue
		/// </summary>
		public virtual int Count {
			get { return m_queueContents.Count - 1; }
		}

		#endregion

		#region constructors

		/// <summary>
		/// 	Construct a new priority queue
		/// </summary>
		public PriorityQueue() {
			m_queueContents = new List<T> {
				default(T)
			};
		}

		#endregion

		#region local methods

		/// <summary>
		/// 	Get the head element of the queue
		/// </summary>
		/// <returns>the head element in the queue</returns>
		public T Peek() {
			if(Count == 0) {
				return default(T);
			}
			return m_queueContents[1];
		}

		/// <summary>
		/// 	Put a new item in the queue
		/// </summary>
		public void Enqueue(T p_value) {
			m_queueContents.Add(p_value);
			_PercolateUp(m_queueContents.Count - 1);
		}

		/// <summary>
		/// 	Returns and remove the head element, maintain heap structure
		/// </summary>
		/// <returns>returns the head element in the queue</returns>
		public T Dequeue() {
			if(Count == 0) {
				return default(T);
			}

			var temp = m_queueContents[1];

			if(m_queueContents.Count > 2) {
				var lastValue = m_queueContents[m_queueContents.Count - 1];

				m_queueContents.RemoveAt(m_queueContents.Count - 1);
				m_queueContents[1] = lastValue;
				_PercolateDown(1);
			} else {
				m_queueContents.RemoveAt(1);
			}

			return temp;
		}

		/// <summary>
		/// 	Restore the heap after an insertion
		/// </summary>
		/// <param name = "p_index">the index to start</param>
		private void _PercolateUp(int p_index) {
			while(_IsParentLarger(p_index)) {
				var parentValue = m_queueContents[p_index >> 1];
				var childValue = m_queueContents[p_index];

				m_queueContents[p_index >> 1] = childValue;
				m_queueContents[p_index] = parentValue;

				p_index = p_index >> 1;
			}
		}

		/// <summary>
		/// 	Restore the heap after a removal
		/// </summary>
		/// <param name = "p_index">the index to start</param>
		private void _PercolateDown(int p_index) {
			while(_IsLeftChildSmaller(p_index) ||
			      _IsRightChildSmaller(p_index)) {
				var compareResult = _CompareChildren(p_index);

				if(compareResult == -1) {
					var parentValue = m_queueContents[p_index];
					var leftChildValue = m_queueContents[p_index << 1];

					m_queueContents[p_index] = leftChildValue;
					m_queueContents[p_index << 1] = parentValue;

					p_index = p_index << 1;
				} else if(compareResult == 1) {
					var parentValue = m_queueContents[p_index];
					var rightChildValue = m_queueContents[(p_index << 1) + 1];

					m_queueContents[p_index] = rightChildValue;
					m_queueContents[(p_index << 1) + 1] = parentValue;

					p_index = (p_index << 1) + 1;
				}
			}
		}

		/// <summary>
		/// 	Returns if parent is larger than child
		/// </summary>
		/// <param name = "p_index">the index to check</param>
		/// <returns>true if parent is larger than child, false otherwise</returns>
		private bool _IsParentLarger(int p_index) {
			if(p_index == 1) {
				return false;
			}
			return m_queueContents[p_index >> 1].CompareTo(m_queueContents[p_index]) > 0;
		}

		/// <summary>
		/// 	Returns if left child is smaller than parent or false if a left 
		/// 	child does not exist.
		/// </summary>
		/// <param name = "p_index">the index to check</param>
		/// <returns>true if left child is smaller than parent, false otherwise</returns>
		private bool _IsLeftChildSmaller(int p_index) {
			if(p_index << 1 >=
			   m_queueContents.Count) {
				return false;
			}

			return m_queueContents[p_index << 1].CompareTo(m_queueContents[p_index]) < 0;
		}

		/// <summary>
		/// 	Returns if the right child is smaller than the parent or false if
		/// 	right child does not exist.
		/// </summary>
		/// <param name = "p_index">the index to check</param>
		/// <returns>true if right child is smaller than parent, false otherwise</returns>
		private bool _IsRightChildSmaller(int p_index) {
			if(p_index << 1 + 1 >=
			   m_queueContents.Count) {
				return false;
			}

			return m_queueContents[(p_index << 1) + 1].CompareTo(m_queueContents[p_index]) < 0;
		}

		/// <summary>
		/// 	Compares children, returns -1 if left child is smaller, 1 if 
		/// 	right child is smaller, or 0 if neither is smaller than parent
		/// </summary>
		/// <param name = "p_index"></param>
		/// <returns>-1 for left child smaller, 1 for right child smaller,
		/// 	0 for neither is smaller than parent</returns>
		private int _CompareChildren(int p_index) {
			var leftChildSmaller = _IsLeftChildSmaller(p_index);
			var rightChildSmaller = _IsRightChildSmaller(p_index);

			if(!leftChildSmaller &&
			   !rightChildSmaller) {
				return 0;
			}

			if(leftChildSmaller && rightChildSmaller) {
				if(m_queueContents[p_index << 1].CompareTo(m_queueContents[(p_index << 1) + 1]) <= 0) {
					return -1;
				}

				return 1;
			}

			if(leftChildSmaller) {
				return -1;
			}

			return 1;
		}

		#endregion
	}
}